home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / agrep / sgrep.c.z / sgrep.c
C/C++ Source or Header  |  1997-09-09  |  73KB  |  2,323 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. #include <stdio.h>
  3. #include <ctype.h>
  4. #include "agrep.h"
  5. #undef    MAXSYM
  6. #define MAXSYM  256
  7. #define MAXMEMBER 8192
  8. #define    CHARTYPE    unsigned char
  9. #undef    MaxError /* don't use agrep.h definition */
  10. #define MaxError 20
  11. #define MAXPATT 256
  12. #undef    MAXLINE
  13. #define MAXLINE 1024
  14. #undef    MAXNAME
  15. #define MAXNAME 256
  16. #undef    MaxCan    /* don't use agrep.h definition */
  17. #define MaxCan  2048
  18. #define BLOCKSIZE    16384
  19. #define MAX_SHIFT_2  4096
  20. #undef    ON
  21. #define ON      1
  22. #undef    OFF
  23. #define OFF    0
  24. #define LOG_ASCII 8
  25. #define LOG_DNA  3
  26. #define MAXMEMBER_1 65536
  27. #define LONG_EXAC  20
  28. #define LONG_APPX  24
  29. #if    ISO_CHAR_SET
  30. #define W_DELIM    256
  31. #else
  32. #define W_DELIM    128
  33. #endif
  34. #include <sys/time.h>
  35.  
  36. extern int tuncompressible();
  37. extern int quick_tcompress();
  38. extern int quick_tuncompress();
  39.  
  40. extern int DELIMITER, OUTTAIL;
  41. extern int D_length, tc_D_length;
  42. extern unsigned char D_pattern[MaxDelimit *2], tc_D_pattern[MaxDelimit *2];
  43. extern int LIMITOUTPUT, LIMITPERFILE, INVERSE;
  44. extern int CurrentByteOffset;
  45. extern int BYTECOUNT;
  46. extern int PRINTOFFSET;
  47. extern int PRINTRECORD;
  48. extern int CONSTANT, COUNT, FNAME, SILENT, FILENAMEONLY, prev_num_of_matched, num_of_matched;
  49. extern int DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  50.          p_size > 16  */
  51. extern WORDBOUND, WHOLELINE, NOUPPER;
  52. extern unsigned char CurrentFileName[],  Progname[]; 
  53. extern unsigned Mask[];
  54. extern unsigned endposition;
  55. extern int agrep_inlen;
  56. extern CHARTYPE *agrep_inbuffer;
  57. extern int agrep_initialfd;
  58. extern FILE *agrep_finalfp;
  59. extern int agrep_outpointer;
  60. extern int agrep_outlen;
  61. extern CHARTYPE * agrep_outbuffer;
  62.  
  63. extern int NEW_FILE, POST_FILTER;
  64.  
  65. extern int EXITONERROR;
  66. extern int errno;
  67. extern int TCOMPRESSED;
  68. extern int EASYSEARCH;
  69. extern char FREQ_FILE[MAX_LINE_LEN], HASH_FILE[MAX_LINE_LEN], STRING_FILE[MAX_LINE_LEN];
  70.  
  71. #if    MEASURE_TIMES
  72. /* timing variables */
  73. extern int OUTFILTER_ms;
  74. extern int FILTERALGO_ms;
  75. extern int INFILTER_ms;
  76. #endif    /*MEASURE_TIMES*/
  77.  
  78. unsigned char BSize;                /* log_c m   */
  79. unsigned char char_map[MAXSYM];
  80.  
  81. /* data area */
  82. int shift_1;
  83. CHARTYPE SHIFT[MAXSYM];
  84. CHARTYPE MEMBER[MAXMEMBER];
  85. CHARTYPE pat[MAXPATT];
  86. unsigned Hashmask;
  87. char MEMBER_1[MAXMEMBER_1];
  88. CHARTYPE TR[MAXSYM];
  89.  
  90. static void initmask();
  91. static void am_preprocess();
  92. static void m_preprocess();
  93. static void prep();
  94. static void prep4();
  95. static void prep_bm();
  96.  
  97. /*
  98.  * General idea behind output processing with delimiters, inverse, compression, etc.
  99.  * CAUTION: In compressed files, we can search ONLY for simple patterns or their ;,.
  100.  * Attempts to search for complex patterns / with errors might lead to spurious matches.
  101.  * 1. Once we find the match, go back and forward to get the delimiters that surround
  102.  *    the matched region.
  103.  * 2. If it is a compressed file, verify that the match is "real" (compressed files
  104.  *    can have pseudo matches hence this filtering step is required).
  105.  * 3. Increment num_of_matched.
  106.  * 4. Process some output options which print stuff before the matched region is
  107.  *    printed.
  108.  * 5. If there is compression, decomress and output the matched region. Otherwise
  109.  *    just output it as is. Remember, from step (1) we know the matched region.
  110.  * 6. If inverse is set, then we must keep track of the end of the last matched region
  111.  *    in the variable lastout. When there is a match, we must print everything from
  112.  *    lastout to the beginning of the current matched region (curtextbegin) and then
  113.  *    update lastout to point to the end of the current matched region (curtextend).
  114.  *    ALSO: if we exit from the main loops, we must output everything from the end
  115.  *    of the last matched region to the end of the input buffer.
  116.  * 7. Delimiter handling in complex patterns is different: there the search is done
  117.  *    for a boolean and of the delimiter pattern and the actual pattern.
  118.  */
  119.  
  120. /* skips over escaped characters */
  121. unsigned char *
  122. mystrchr(s, c)
  123. unsigned char *s;
  124. int c;
  125. {
  126.     unsigned char    *t = s;
  127.  
  128.     while (*t) {
  129.         if (*t == '\\') t++;
  130.         else if (c == *t) return t;
  131.         t ++;
  132.     }
  133.     return NULL;
  134. }
  135.  
  136. void
  137. char_tr(pat, m)
  138. unsigned char *pat;
  139. int *m;
  140. {
  141.     int i;
  142.     unsigned char temp[MAXPATT];
  143.     for(i=0; i<MAXSYM; i++) TR[i] = i;
  144.     if(NOUPPER) {
  145.         for(i=0; i<MAXSYM; i++)
  146.             if (isupper(i)) TR[i] = TR[tolower(i)];
  147.         /* for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A'; */
  148.     }
  149.     /*
  150.     if(WORDBOUND) {
  151.         for(i=0; i<MAXSYM; i++) {
  152.             if(!isalnum(i)) TR[i] = W_DELIM;removed by Udi.
  153.             we don't use the trick of making the boundary W_delim anymore.
  154.             It's too buggy otherwise and it's not necessary.
  155.         }
  156.     }
  157.     removed by bg 11/8/94
  158.     */
  159.     if(WHOLELINE) {
  160.         memcpy(temp, pat, *m);
  161.         pat[0] = '\n';
  162.         memcpy(pat+1, temp, *m);
  163.         pat[*m+1] = '\n';
  164.         pat[*m+2] = 0;
  165.         *m = *m + 2;
  166.     }
  167. }
  168.  
  169. int
  170. sgrep(in_pat, in_m, fd, D, samepattern)
  171. CHARTYPE *in_pat;  
  172. int fd, in_m, D;
  173. {
  174.     CHARTYPE patbuf[MAXLINE];
  175.     CHARTYPE *pat = patbuf;
  176.     int m = in_m;
  177.     CHARTYPE *text; /* input text stream */
  178.     int offset = 2*MAXLINE;
  179.     int buf_end, num_read, i, start, end, residue = 0;
  180.     int first_time = 1;
  181.     CHARTYPE *oldpat = pat;
  182.     int k, j, oldm = m;
  183.     static CHARTYPE newpat[MAXLINE];    /* holds compressed version */
  184.     static int newm;
  185. #if    MEASURE_TIMES
  186.     static struct timeval initt, finalt;
  187. #endif
  188.     CHARTYPE *tempbuf;
  189.     int    oldCurrentByteOffset;
  190.  
  191.     strncpy(pat, in_pat, MAXLINE);
  192.     pat[MAXLINE-1] = '\0';
  193.  
  194. #define PROCESS_PATTERN \
  195.     if (!CONSTANT) {\
  196.         if( (pat[0] == '^') || (pat[0] == '$') ) pat[0] = '\n';\
  197.         if ((m>1) && (pat[m-2] != '\\') && ((pat[m-1] == '^') || (pat[m-1] == '$'))) pat[m-1] = '\n';\
  198.     }\
  199.     /* whether constant or not, interpret the escape character */\
  200.     for (k=0; k<m; k++) {\
  201.         if (pat[k] == '\\') {\
  202.             for (j=k; j<m; j++)\
  203.                 pat[j] = pat[j+1]; /* including '\0' */\
  204.             m--;\
  205.         }\
  206.     }\
  207.     char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */\
  208.     if(m >= MAXPATT) {\
  209.         fprintf(stderr, "%s: pattern too long (has > %d chars)\n", Progname, MAXPATT);\
  210.         if (!EXITONERROR) {\
  211.             errno = AGREP_ERROR;\
  212.             return -1;\
  213.         }\
  214.         else exit(2);\
  215.     }\
  216.     if(D == 0) {\
  217.         if(m > LONG_EXAC) m_preprocess(pat);\
  218.         else prep_bm(pat, m);\
  219.     }\
  220.     else if (DNA) prep4(pat, m);\
  221.     else     if(m >= LONG_APPX) am_preprocess(pat);\
  222.     else {\
  223.         prep(pat, m, D);\
  224.         initmask(pat, Mask, m, 0, &endposition);\
  225.     }
  226.  
  227. #if    AGREP_POINTER
  228.     if (fd != -1) {
  229. #endif    /*AGREP_POINTER*/
  230.         alloc_buf(fd, &text, 2*BLOCKSIZE+2*MAXLINE+MAXPATT);
  231.         text[offset-1] = '\n';  /* initial case */
  232.         for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  233.         start = offset;   
  234.         if(WHOLELINE) {
  235.             start--;
  236.             CurrentByteOffset --;
  237.         }
  238.  
  239.         while( (num_read = fill_buf(fd, text+offset, 2*BLOCKSIZE)) > 0) 
  240.         {
  241.             buf_end = end = offset + num_read -1 ;
  242.             oldCurrentByteOffset = CurrentByteOffset;
  243.  
  244.             if (first_time) {
  245.                 if ((TCOMPRESSED == ON) && tuncompressible(text+offset, num_read)) {
  246.                     EASYSEARCH = text[offset+SIGNATURE_LEN-1];
  247.                     start += SIGNATURE_LEN;
  248.                     CurrentByteOffset += SIGNATURE_LEN;
  249.                     if (!EASYSEARCH) {
  250.                         fprintf(stderr, "not compressed for easy-search: can miss some matches in: %s\n", CurrentFileName);
  251.                     }
  252. #if    MEASURE_TIMES
  253.                     gettimeofday(&initt, NULL);
  254. #endif    /*MEASURE_TIMES*/
  255.                     if (samepattern || ((newm = quick_tcompress(FREQ_FILE, HASH_FILE, pat, m, newpat, MAXLINE-8, EASYSEARCH)) > 0)) {
  256.                         oldm = m;
  257.                         oldpat = pat;
  258.                         m = newm;
  259.                         pat = newpat;
  260.                     }
  261. #if    MEASURE_TIMES
  262.                     gettimeofday(&finalt, NULL);
  263.                     INFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  264. #endif    /*MEASURE_TIMES*/
  265.                 }
  266.                 else TCOMPRESSED = OFF;
  267.  
  268.                 PROCESS_PATTERN    /* must be AFTER we know that it is a compressed pattern... */
  269.  
  270.                 for(i=1; i<=m; i++) text[2*BLOCKSIZE+offset+i] = pat[m-1];
  271.                 /* to make sure the skip loop in bm() won't go out of bound in later iterations */
  272.                 first_time = 0;
  273.             }
  274.  
  275.                         if (!DELIMITER) {
  276.                                 while ((text[end]  != '\n') && (end > offset)) end--;
  277.                                 text[start-1] = '\n';
  278.                         }
  279.                         else {
  280.                                 unsigned char *newbuf = text + end + 1;
  281.                                 newbuf = backward_delimiter(newbuf, text+offset, D_pattern, D_length, OUTTAIL);        /* see agrep.c/'d' */
  282.                 if (newbuf < text+offset+D_length) newbuf = text + end + 1;
  283.                                 end = newbuf - text - 1;
  284.                                 memcpy(text+start-D_length, D_pattern, D_length);
  285.                         }
  286.             residue = buf_end - end + 1 ;
  287.  
  288.             /* SGREP_PROCESS */
  289.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  290.             if(D==0)  {
  291.                 if(m > LONG_EXAC) {
  292.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  293.                         free_buf(fd, text);
  294.                         return -1;
  295.                     }
  296.                 }
  297.                 else {
  298.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  299.                         free_buf(fd, text);
  300.                         return -1;
  301.                     }
  302.                 }
  303.             }
  304.             else {
  305.                 if(DNA) {
  306.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  307.                         free_buf(fd, text);
  308.                         return -1;
  309.                     }
  310.                 }
  311.                 else {
  312.                     if(m >= LONG_APPX) {
  313.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  314.                             free_buf(fd, text);
  315.                             return -1;
  316.                         }
  317.                     }
  318.                     else {
  319.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  320.                             free_buf(fd, text);
  321.                             return -1;
  322.                         }
  323.                     }
  324.                 }
  325.             }
  326.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {
  327.                 if (agrep_finalfp != NULL)
  328.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  329.                 else {
  330.                     int outindex;
  331.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  332.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  333.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  334.                     }
  335.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  336.                         OUTPUT_OVERFLOW;
  337.                         free_buf(fd, text);
  338.                         return -1;
  339.                     }
  340.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  341.                     agrep_outpointer += outindex;
  342.                 }
  343.                 free_buf(fd, text);
  344.                 NEW_FILE = OFF;
  345.                 return 0; 
  346.             }
  347.  
  348.             CurrentByteOffset = oldCurrentByteOffset + end - start + 1;    /* for a new iteration: avoid complicated calculations below */
  349.             start = offset - residue ;
  350.             if(start < MAXLINE) {
  351.                 start = MAXLINE; 
  352.             }
  353.             strncpy(text+start, text+end, residue);
  354.             start++;
  355.             if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  356.                 ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) {
  357.                 free_buf(fd, text);
  358.                 return 0;    /* done */
  359.             }
  360.         } /* end of while(num_read = ...) */
  361.                 if (!DELIMITER) {
  362.                         text[start-1] = '\n';
  363.                         text[start+residue] = '\n';
  364.                 }
  365.                 else {
  366.                         if (start > D_length) memcpy(text+start-D_length, D_pattern, D_length);
  367.                         memcpy(text+start+residue, D_pattern, D_length);
  368.                 }
  369.         end = start + residue - 2;
  370.                 if(residue > 1) {
  371.             /* SGREP_PROCESS */
  372.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  373.             if(D==0)  {
  374.                 if(m > LONG_EXAC) {
  375.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  376.                         free_buf(fd, text);
  377.                         return -1;
  378.                     }
  379.                 }
  380.                 else {
  381.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  382.                         free_buf(fd, text);
  383.                         return -1;
  384.                     }
  385.                 }
  386.             }
  387.             else {
  388.                 if(DNA) {
  389.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  390.                         free_buf(fd, text);
  391.                         return -1;
  392.                     }
  393.                 }
  394.                 else {
  395.                     if(m >= LONG_APPX) {
  396.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  397.                             free_buf(fd, text);
  398.                             return -1;
  399.                         }
  400.                     }
  401.                     else {
  402.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  403.                             free_buf(fd, text);
  404.                             return -1;
  405.                         }
  406.                     }
  407.                 }
  408.             }
  409.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {
  410.                 if (agrep_finalfp != NULL)
  411.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  412.                 else {
  413.                     int outindex;
  414.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  415.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  416.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  417.                     }
  418.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  419.                         OUTPUT_OVERFLOW;
  420.                         free_buf(fd, text);
  421.                         return -1;
  422.                     }
  423.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  424.                     agrep_outpointer += outindex;
  425.                 }
  426.                 free_buf(fd, text);
  427.                 NEW_FILE = OFF;
  428.                 return 0; 
  429.             }
  430.                 }
  431.         free_buf(fd, text);
  432.         return 0;
  433. #if    AGREP_POINTER
  434.     }
  435.     else {    /* as if only one iteration of the while-loop and offset = 0 */
  436.         tempbuf = (CHARTYPE*)malloc(m);
  437.         text = (CHARTYPE *)agrep_inbuffer;
  438.         num_read = agrep_inlen;
  439.         start = 0;
  440.         buf_end = end = num_read - 1;
  441. #if    0
  442.         if (WHOLELINE) {
  443.             start --;
  444.             CurrentByteOffset --;
  445.         }
  446. #endif
  447.         if ((TCOMPRESSED == ON) && tuncompressible(text+1, num_read)) {
  448.             EASYSEARCH = text[offset+SIGNATURE_LEN-1];
  449.             start += SIGNATURE_LEN;
  450.             CurrentByteOffset += SIGNATURE_LEN;
  451.             if (!EASYSEARCH) {
  452.                 fprintf(stderr, "not compressed for easy-search: can miss some matches in: %s\n", CurrentFileName);
  453.             }
  454. #if    MEASURE_TIMES
  455.             gettimeofday(&initt, NULL);
  456. #endif    /*MEASURE_TIMES*/
  457.             if (samepattern || ((newm = quick_tcompress(FREQ_FILE, HASH_FILE, pat, m, newpat, MAXLINE-8, EASYSEARCH)) > 0)) {
  458.                 oldm = m;
  459.                 oldpat = pat;
  460.                 m = newm;
  461.                 pat = newpat;
  462.             }
  463. #if    MEASURE_TIMES
  464.             gettimeofday(&finalt, NULL);
  465.             INFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  466. #endif    /*MEASURE_TIMES*/
  467.         }
  468.         else TCOMPRESSED = OFF;
  469.  
  470.         PROCESS_PATTERN    /* must be after we know whether it is compressed or not */
  471.  
  472.         memcpy(tempbuf, text+end+1, m);    /* save portion being overwritten */
  473.         for(i=1; i<=m; i++) text[end+i] = pat[m-1];
  474.         /* to make sure the skip loop in bm() won't go out of bound in later iterations */
  475.  
  476.                         if (!DELIMITER)
  477.                                 while(text[end]  != '\n' && end > 1) end--;
  478.                         else {
  479.                                 unsigned char *newbuf = text + end + 1;
  480.                                 newbuf = backward_delimiter(newbuf, text, D_pattern, D_length, OUTTAIL);        /* see agrep.c/'d' */
  481.                 if (newbuf < text+offset+D_length) newbuf = text + end + 1;
  482.                                 end = newbuf - text - 1;
  483.                         }
  484.                         /* text[0] = text[end] = r_newline; : the user must ensure that the delimiter is there at text[0] and occurs somewhere before text[end ] */
  485.  
  486.             /* An exact copy of the above SGREP_PROCESS */
  487.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  488.             if(D==0)  {
  489.                 if(m > LONG_EXAC) {
  490.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  491.                         free_buf(fd, text);
  492.                         memcpy(text+end+1, tempbuf, m); /* restore */
  493.                         free(tempbuf);
  494.                         return -1;
  495.                     }
  496.                 }
  497.                 else {
  498.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  499.                         free_buf(fd, text);
  500.                         memcpy(text+end+1, tempbuf, m); /* restore */
  501.                         free(tempbuf);
  502.                         return -1;
  503.                     }
  504.                 }
  505.             }
  506.             else {
  507.                 if(DNA) {
  508.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  509.                         free_buf(fd, text);
  510.                         memcpy(text+end+1, tempbuf, m); /* restore */
  511.                         free(tempbuf);
  512.                         return -1;
  513.                     }
  514.                 }
  515.                 else {
  516.                     if(m >= LONG_APPX) {
  517.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  518.                             free_buf(fd, text);
  519.                             memcpy(text+end+1, tempbuf, m); /* restore */
  520.                             free(tempbuf);
  521.                             return -1;
  522.                         }
  523.                     }
  524.                     else {
  525.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  526.                             free_buf(fd, text);
  527.                             memcpy(text+end+1, tempbuf, m); /* restore */
  528.                             free(tempbuf);
  529.                             return -1;
  530.                         }
  531.                     }
  532.                 }
  533.             }
  534.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {    /* externally set */
  535.                 if (agrep_finalfp != NULL)
  536.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  537.                 else {
  538.                     int outindex;
  539.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  540.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  541.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  542.                     }
  543.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  544.                         OUTPUT_OVERFLOW;
  545.                         free_buf(fd, text);
  546.                         memcpy(text+end+1, tempbuf, m); /* restore */
  547.                         free(tempbuf);
  548.                         return -1;
  549.                     }
  550.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  551.                     agrep_outpointer += outindex;
  552.                 }
  553.                 free_buf(fd, text);
  554.                 NEW_FILE = OFF;
  555.             }
  556.  
  557.         memcpy(text+end+1, tempbuf, m); /* restore */
  558.         free(tempbuf);
  559.         return 0;
  560.     }
  561. #endif    /*AGREP_POINTER*/
  562. } /* end sgrep */
  563.  
  564. /* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  565. pat[m-1] such that the skip loop is guaranteed to terminated */
  566.  
  567. int
  568. bm(pat, m, text, textend, oldpat, oldm)
  569. CHARTYPE *text, *textend, *pat, *oldpat;
  570. int m, oldm;
  571. {
  572.     int PRINTED = 0;
  573.     register int shift;
  574.     register int  m1, j, d1; 
  575.     CHARTYPE *textbegin = text;
  576.     int newlen;
  577.     CHARTYPE *textstart;
  578.     CHARTYPE *curtextbegin;
  579.     CHARTYPE *curtextend;
  580. #if    MEASURE_TIMES
  581.     struct timeval initt, finalt;
  582. #endif
  583.     CHARTYPE *lastout = text;
  584.  
  585.     d1 = shift_1;    /* at least 1 */
  586.     m1 = m - 1;
  587.     shift = 0;       
  588.     while (text <= textend) {
  589.         textstart = text;
  590.         shift = SHIFT[*(text += shift)];
  591.         while(shift) {         
  592.             shift = SHIFT[*(text += shift)];
  593.             shift = SHIFT[*(text += shift)];
  594.             shift = SHIFT[*(text += shift)];
  595.         }
  596.         CurrentByteOffset += text - textstart;
  597.         j = 0;
  598.         while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  599.             if(++j == m)  break;       /* if statement can be saved, but for safty ... */
  600.         }
  601.         if (j == m ) { 
  602.             if(text > textend) return 0;
  603.             if(WORDBOUND) {
  604.                 if(isalnum(*(text+1))) goto CONT;    /* as if there was no match */
  605.                 if(isalnum(*(text-m))) goto CONT;    /* as if there was no match */
  606.                 /* changed by Udi 11/7/94 to avoid having to set TR[] to W_delim */
  607.             }
  608.  
  609.             if (TCOMPRESSED == ON) {
  610.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  611.                 if (!DELIMITER) {
  612.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  613.                     if (*curtextbegin == '\n') curtextbegin ++;
  614.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  615.                     if (*curtextend == '\n') curtextend ++;
  616.                 }
  617.                 else {
  618.                     curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  619.                     curtextend = forward_delimiter(text+1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  620.                 }
  621.             }
  622.             else {
  623.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  624.                 if (!DELIMITER) {
  625.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  626.                     if (*curtextbegin == '\n') curtextbegin ++;
  627.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  628.                     if (*curtextend == '\n') curtextend ++;
  629.                 }
  630.                 else {
  631.                     curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  632.                     curtextend = forward_delimiter(text+1, textend, D_pattern, D_length, OUTTAIL);
  633.                 }
  634.             }
  635.  
  636.             if (TCOMPRESSED == ON) {
  637. #if     MEASURE_TIMES
  638.                                 gettimeofday(&initt, NULL);
  639. #endif  /*MEASURE_TIMES*/
  640.                 if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text - curtextbegin + m, EASYSEARCH))
  641.                     goto CONT;    /* as if there was no match */
  642. #if     MEASURE_TIMES
  643.                                 gettimeofday(&finalt, NULL);
  644.                                 FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  645. #endif  /*MEASURE_TIMES*/
  646.             }
  647.  
  648.             textbegin = curtextend; /* (curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  649.             num_of_matched++;
  650.             if(FILENAMEONLY) return 0;
  651.             if(!COUNT) {
  652.                 if (!INVERSE) {
  653.                     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  654.                         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  655.                         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  656.                         if (agrep_finalfp != NULL)
  657.                             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  658.                         else {
  659.                             int outindex;
  660.                             if (prevstring[0] != '\0') {
  661.                                 if(agrep_outpointer + 1 >= agrep_outlen) {
  662.                                     OUTPUT_OVERFLOW;
  663.                                     return -1;
  664.                                 }
  665.                                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  666.                             }
  667.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  668.                                     (CurrentFileName[outindex] != '\0'); outindex++) {
  669.                                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  670.                             }
  671.                             if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+2>=agrep_outlen)) {
  672.                                 OUTPUT_OVERFLOW;
  673.                                 return -1;
  674.                             }
  675.                             else {
  676.                                 agrep_outbuffer[agrep_outpointer+outindex++] = ':';
  677.                                 agrep_outbuffer[agrep_outpointer+outindex++] = nextchar;
  678.                             }
  679.                             agrep_outpointer += outindex;
  680.                         }
  681.                         NEW_FILE = OFF;
  682.                         PRINTED = 1;
  683.                     }
  684.  
  685.                     if(BYTECOUNT) {
  686.                         if (agrep_finalfp != NULL)
  687.                             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  688.                         else {
  689.                             char s[32];
  690.                             int  outindex;
  691.                             sprintf(s, "%d=", CurrentByteOffset);
  692.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  693.                                     (s[outindex] != '\0'); outindex++) {
  694.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  695.                             }
  696.                             if (s[outindex] != '\0') {
  697.                                 OUTPUT_OVERFLOW;
  698.                                 return -1;
  699.                             }
  700.                             agrep_outpointer += outindex;
  701.                         }
  702.                         PRINTED = 1;
  703.                     }
  704.  
  705.                     if (PRINTOFFSET) {
  706.                         if (agrep_finalfp != NULL)
  707.                             fprintf(agrep_finalfp, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  708.                         else {
  709.                             char s[32];
  710.                             int outindex;
  711.                             sprintf(s, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  712.                             for (outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  713.                                      (s[outindex] != '\0'); outindex ++) {
  714.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  715.                             }
  716.                             if (s[outindex] != '\0') {
  717.                                 OUTPUT_OVERFLOW;
  718.                                 return -1;
  719.                             }
  720.                             agrep_outpointer += outindex;
  721.                         }
  722.                         PRINTED = 1;
  723.                     }
  724.  
  725.                     CurrentByteOffset += textbegin - text;
  726.                     text = textbegin;
  727.  
  728.  
  729.                     if (PRINTRECORD) {
  730.                     if (TCOMPRESSED == ON) {
  731. #if    MEASURE_TIMES
  732.                         gettimeofday(&initt, NULL);
  733. #endif    /*MEASURE_TIMES*/
  734.                         if (agrep_finalfp != NULL)
  735.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  736.                         else {
  737.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  738.                                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  739.                                     OUTPUT_OVERFLOW;
  740.                                     return -1;
  741.                                 }
  742.                                 agrep_outpointer += newlen;
  743.                             }
  744.                         }
  745. #if    MEASURE_TIMES
  746.                         gettimeofday(&finalt, NULL);
  747.                         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  748. #endif    /*MEASURE_TIMES*/
  749.                     }
  750.                     else {
  751.                         if (agrep_finalfp != NULL) {
  752.                             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  753.                         }
  754.                         else {
  755.                             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  756.                                 OUTPUT_OVERFLOW;
  757.                                 return -1;
  758.                             }
  759.                             memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  760.                             agrep_outpointer += curtextend - curtextbegin;
  761.                         }
  762.                     }
  763.                     }
  764.                     else if (PRINTED) {
  765.                         if (agrep_finalfp != NULL) fputc('\n', agrep_finalfp);
  766.                         else agrep_outbuffer[agrep_outpointer ++] = '\n';
  767.                         PRINTED = 0;
  768.                     }
  769.                 }
  770.                 else {    /* INVERSE */
  771.                     if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  772.                         if (agrep_finalfp != NULL)
  773.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  774.                         else {
  775.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  776.                                 if (newlen + agrep_outpointer >= agrep_outlen) {
  777.                                     OUTPUT_OVERFLOW;
  778.                                     return -1;
  779.                                 }
  780.                                 agrep_outpointer += newlen;
  781.                             }
  782.                         }
  783.                         lastout=textbegin;
  784.                         CurrentByteOffset += textbegin - text;
  785.                         text = textbegin;
  786.                     }
  787.                     else { /* NOT TCOMPRESSED */
  788.                         if (agrep_finalfp != NULL)
  789.                             fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  790.                         else {
  791.                             if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  792.                                 OUTPUT_OVERFLOW;
  793.                                 return -1;
  794.                             }
  795.                             memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  796.                             agrep_outpointer += (curtextbegin - lastout);
  797.                         }
  798.                         lastout=textbegin;
  799.                         CurrentByteOffset += textbegin - text;
  800.                         text = textbegin;
  801.                     } /* TCOMPRESSED */
  802.                 } /* INVERSE */
  803.             }
  804.             else {    /* COUNT */
  805.                 CurrentByteOffset += textbegin - text;
  806.                 text = textbegin;
  807.             }
  808.             if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  809.                 ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  810.  
  811. CONT:
  812.             shift = 1;
  813.         }
  814.         else shift = d1;
  815.     }
  816.  
  817.     if (INVERSE && !COUNT && (lastout <= textend)) {
  818.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  819.             if (agrep_finalfp != NULL)
  820.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  821.             else {
  822.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  823.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  824.                         OUTPUT_OVERFLOW;
  825.                         return -1;
  826.                     }
  827.                     agrep_outpointer += newlen;
  828.                 }
  829.             }
  830.         }
  831.         else { /* NOT TCOMPRESSED */
  832.             if (agrep_finalfp != NULL)
  833.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  834.             else {
  835.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  836.                     OUTPUT_OVERFLOW;
  837.                     return -1;
  838.                 }
  839.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  840.                 agrep_outpointer += (textend - lastout + 1);
  841.             }
  842.         } /* TCOMPRESSED */
  843.     }
  844.  
  845.     return 0;
  846. }
  847.  
  848. /* initmask() initializes the mask table for the pattern                    */ 
  849. /* endposition is a mask for the endposition of the pattern                 */
  850. /* endposition will contain k mask bits if the pattern contains k fragments */
  851. static void
  852. initmask(pattern, Mask, m, D, endposition)
  853. CHARTYPE *pattern; 
  854. unsigned *Mask; 
  855. register int m, D; 
  856. unsigned *endposition;
  857. {
  858.     register unsigned Bit1, c;
  859.     register int i, j, frag_num;
  860.  
  861.     /* Bit1 = 1 << 31;*/    /* the first bit of Bit1 is 1, others 0.  */
  862.     Bit1 = (unsigned)0x80000000;
  863.     frag_num = D+1; 
  864.     *endposition = 0;
  865.     for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  866.     *endposition = *endposition >> (m - frag_num);
  867.     for(i = 0; i < m; i++) 
  868.         if (pattern[i] == '^' || pattern[i] == '$') {
  869.             pattern[i] = '\n'; 
  870.         }
  871.     for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  872.     for(i = 0; i < m; i++)     /* initialize the mask table */
  873.     {  
  874.         c = pattern[i];
  875.         for ( j = 0; j < m; j++)
  876.             if( c == pattern[j] )
  877.                 Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  878.     }
  879. }
  880.  
  881. static void
  882. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  883. CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  884. register int M, D;
  885. {
  886.     register int i, j, k, p, shift;
  887.     register unsigned m;
  888.     unsigned hash, b_size = 3;
  889.     m = M/(D+1);
  890.     p = M - m*(D+1);
  891.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  892.     for (i = M-1; i>=p ; i--) {
  893.         shift = (M-1-i)%m;
  894.         hash = Pattern[i];
  895.         if((int)(SHIFT[hash]) > (int)(shift)) SHIFT[hash] = shift;
  896.     }
  897. #ifdef DEBUG
  898.     for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  899.     printf("\n");
  900. #endif
  901.     shift_1 = m;
  902.     for(i=0; i<D+1; i++) {
  903.         j = M-1 - m*i;
  904.         for(k=1; k<m; k++) {
  905.             for(p=0; p<D+1; p++) 
  906.                 if(Pattern[j-k] == Pattern[M-1-m*p]) 
  907.                     if(k < shift_1) shift_1 = k;
  908.         }
  909.     }
  910. #ifdef DEBUG
  911.     printf("\nshift_1 = %d", shift_1);
  912. #endif
  913.     if(shift_1 == 0) shift_1 = 1;
  914.     for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  915.     if (m < 3) b_size = m;
  916.     for(i=0; i<D+1; i++) {
  917.         j = M-1 - m*i;
  918.         hash = 0;
  919.         for(k=0; k<b_size; k++) {
  920.             hash = (hash << 2) + Pattern[j-k];
  921.         }
  922. #ifdef DEBUG
  923.         printf(" hash = %d,", hash);
  924. #endif
  925.         MEMBER[hash] = 1;
  926.     }
  927. }
  928.  
  929. int
  930. agrep( pat, M, text, textend, D, oldpat, oldM) 
  931. int M, D, oldM; 
  932. register CHARTYPE *text, *textend, *pat, *oldpat;
  933. {
  934.     register int i;
  935.     register int m = M/(D+1);
  936.     register CHARTYPE *textbegin;
  937.     CHARTYPE *textstart;
  938.     register int shift, HASH;
  939.     int  j=0, k, d1;
  940.     int  n, cdx;
  941.     int  Candidate[MaxCan][2], round, lastend=0;
  942.     unsigned R1[MaxError+1], R2[MaxError+1]; 
  943.     register unsigned int r1, endpos, c; 
  944.     unsigned currentpos;
  945.     unsigned Bit1;
  946.     unsigned r_newline;
  947.     int oldbyteoffset;
  948.     CHARTYPE *lastout = text;
  949.     int newlen;
  950.  
  951.     Candidate[0][0] = Candidate[0][1] = 0; 
  952.     d1 = shift_1;
  953.     cdx = 0;
  954.     if(m < 3) r1 = m;
  955.     else r1 = 3;
  956.     textbegin = text;
  957.     shift = m-1;
  958.     while (text < textend) {
  959.         textstart = text;
  960.         shift = SHIFT[*(text += shift)];
  961.         while(shift) {
  962.             shift = SHIFT[*(text += shift)];
  963.             shift = SHIFT[*(text += shift)];
  964.         }
  965.         CurrentByteOffset += text - textstart;
  966.         j = 1; 
  967.         HASH = *text;
  968.         while(j < r1) { 
  969.             HASH = (HASH << 2) + *(text-j);
  970.             j++; 
  971.         }
  972.         if (MEMBER[HASH]) { 
  973.             i = text - textbegin;
  974.             if((i - M - D - 10) > Candidate[cdx][1]) {     
  975.                 Candidate[++cdx][0] = i-M-D-2;
  976.                 Candidate[cdx][1] = i+M+D; 
  977.             }
  978.             else Candidate[cdx][1] = i+M+D;
  979.             shift = d1;
  980.         }
  981.         else shift = d1;
  982.     }
  983.  
  984.     CurrentByteOffset += (textbegin - text);
  985.     text = textbegin;
  986.     n = textend - textbegin;
  987.     r_newline = '\n';
  988.     /* for those candidate areas, find the D-error matches                     */
  989.     if(Candidate[1][0] < 0) Candidate[1][0] = 0;
  990.     endpos = endposition;                /* the mask table and the endposition */
  991.     /* Bit1 = (1 << 31); */
  992.     Bit1 = (unsigned)0x80000000;
  993.     oldbyteoffset = CurrentByteOffset;
  994.     for(round = 0; round <= cdx; round++)
  995.     {  
  996.         i = Candidate[round][0] ; 
  997.         if(Candidate[round][1] > n) Candidate[round][1] = n;
  998.         if(i < 0) i = 0;
  999.         CurrentByteOffset = oldbyteoffset+i;
  1000.         R1[0] = R2[0] = ~0;
  1001.         R1[1] = R2[1] = ~Bit1;
  1002.         for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];
  1003.         while (i < Candidate[round][1])                     
  1004.         {  
  1005.             c = text[i++];
  1006.             CurrentByteOffset ++;
  1007.             if(c == r_newline) {
  1008.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  1009.             }
  1010.             r1 = Mask[c];
  1011.             R1[0] = (R2[0] >> 1) | r1;
  1012.             for(k=1; k<=D; k++)
  1013.                 R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  1014.             if((R1[D] & endpos) == 0) { 
  1015.                 num_of_matched++;
  1016.                 if(FILENAMEONLY) return 0; 
  1017.                 currentpos = i;
  1018.                 if(i <= lastend) {
  1019.                     CurrentByteOffset += lastend - i;
  1020.                     i = lastend;
  1021.                 }
  1022.                 else {
  1023.                     int oldcurrentpos = currentpos;
  1024.                     if (-1 == s_output(text, ¤tpos, textbegin, textend, &lastout, pat, M, oldpat, oldM)) return -1;
  1025.                     CurrentByteOffset += currentpos - oldcurrentpos;
  1026.                     i = currentpos; 
  1027.                 }
  1028.                 lastend = i;
  1029.                 for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  1030.                 if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  1031.                     ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  1032.             }
  1033.  
  1034.             /* copying the code to save a few instructions.
  1035.             you need to understand the shift-or algorithm
  1036.             to figure this one... */
  1037.  
  1038.             c = text[i++];
  1039.             CurrentByteOffset ++;
  1040.             if(c == r_newline) {
  1041.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  1042.             }
  1043.             r1 = Mask[c];
  1044.             R2[0] = (R1[0] >> 1) | r1;
  1045.             for(k = 1; k <= D; k++)
  1046.                 R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  1047.             if((R2[D] & endpos) == 0) { 
  1048.                 currentpos = i;
  1049.                 num_of_matched++;
  1050.                 if(FILENAMEONLY) return 0; 
  1051.                 if(i <= lastend) {
  1052.                     CurrentByteOffset += lastend - i;
  1053.                     i = lastend;
  1054.                 }
  1055.                 else {
  1056.                     int oldcurrentpos = currentpos;
  1057.                     if (-1 == s_output(text, ¤tpos, textbegin, textend, &lastout, pat, M, oldpat, oldM)) return -1;
  1058.                     CurrentByteOffset += currentpos - oldcurrentpos;
  1059.                     i = currentpos; 
  1060.                 }
  1061.                 lastend = i;
  1062.                 for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  1063.                 if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  1064.                     ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  1065.             }
  1066.         }
  1067.     }
  1068.  
  1069.  
  1070.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1071.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1072.             if (agrep_finalfp != NULL)
  1073.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1074.             else {
  1075.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1076.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1077.                         OUTPUT_OVERFLOW;
  1078.                         return -1;
  1079.                     }
  1080.                     agrep_outpointer += newlen;
  1081.                 }
  1082.             }
  1083.         }
  1084.         else { /* NOT TCOMPRESSED */
  1085.             if (agrep_finalfp != NULL)
  1086.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1087.             else {
  1088.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1089.                     OUTPUT_OVERFLOW;
  1090.                     return -1;
  1091.                 }
  1092.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1093.                 agrep_outpointer += (textend - lastout + 1);
  1094.             }
  1095.         } /* TCOMPRESSED */
  1096.     }
  1097.  
  1098.     return 0;
  1099. }
  1100.  
  1101. /* Don't update CurrentByteOffset here: done by caller */
  1102. int
  1103. s_output(text, i, textbegin, textend, lastout, pat, m, oldpat, oldm) 
  1104. int *i;    /* in, out */
  1105. int m, oldm; 
  1106. CHARTYPE *text, *textbegin, *textend, *pat, *oldpat;
  1107. CHARTYPE **lastout;    /* in, out */
  1108. {
  1109.     int PRINTED = 0;
  1110.     int newlen; 
  1111.     int oldi;
  1112.     CHARTYPE *curtextbegin;
  1113.     CHARTYPE *curtextend;
  1114. #if    MEASURE_TIMES
  1115.     struct timeval initt, finalt;
  1116. #endif
  1117.  
  1118.     if(SILENT) return 0;
  1119.     if (TCOMPRESSED == ON) {
  1120.         if (!DELIMITER) {
  1121.             curtextbegin = text + *i; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1122.             if (*curtextbegin == '\n') curtextbegin ++;
  1123.             curtextend = text + *i /* + 1 agrep() has i++ */; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1124.             if (*curtextend == '\n') curtextend ++;
  1125.         }
  1126.         else {
  1127.             curtextbegin = backward_delimiter(text + *i, text, tc_D_pattern, tc_D_length, OUTTAIL);
  1128.             curtextend = forward_delimiter(text + *i /* + 1 agrep() has i++ */, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1129.         }
  1130.     }
  1131.     else {
  1132.         if (!DELIMITER) {
  1133.             curtextbegin = text + *i; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1134.             if (*curtextbegin == '\n') curtextbegin ++;
  1135.             curtextend = text + *i /* + 1 agrep() has i++ */; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1136.             if (*curtextend == '\n') curtextend ++;
  1137.         }
  1138.         else {
  1139.             curtextbegin = backward_delimiter(text + *i, text, D_pattern, D_length, OUTTAIL);
  1140.             curtextend = forward_delimiter(text + *i /* + 1 agrep() has i++ */, textend, D_pattern, D_length, OUTTAIL);
  1141.         }
  1142.     }
  1143.  
  1144.     if (TCOMPRESSED == ON) {
  1145. #if     MEASURE_TIMES
  1146.         gettimeofday(&initt, NULL);
  1147. #endif  /*MEASURE_TIMES*/
  1148.         if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text  + *i - curtextbegin + m, EASYSEARCH)) {
  1149.             num_of_matched --;
  1150.             return 0;
  1151.         }
  1152. #if     MEASURE_TIMES
  1153.         gettimeofday(&finalt, NULL);
  1154.         FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1155. #endif  /*MEASURE_TIMES*/
  1156.     }
  1157.  
  1158.     textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1159.     oldi = *i;
  1160.     *i += textbegin - (text + *i);
  1161.     if(COUNT) return 0;
  1162.  
  1163.  
  1164.     if (INVERSE) {
  1165.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1166.             if (agrep_finalfp != NULL)
  1167.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, *lastout, curtextbegin - *lastout, agrep_finalfp, -1, EASYSEARCH);
  1168.             else {
  1169.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, *lastout, curtextbegin - *lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1170.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1171.                         OUTPUT_OVERFLOW;
  1172.                         return -1;
  1173.                     }
  1174.                     agrep_outpointer += newlen;
  1175.                 }
  1176.             }
  1177.             *lastout=textbegin;
  1178.             CurrentByteOffset += textbegin - text;
  1179.             text = textbegin;
  1180.         }
  1181.         else { /* NOT TCOMPRESSED */
  1182.             if (agrep_finalfp != NULL)
  1183.                 fwrite(*lastout, 1, curtextbegin-*lastout, agrep_finalfp);
  1184.             else {
  1185.                 if (curtextbegin - *lastout + agrep_outpointer >= agrep_outlen) {
  1186.                     OUTPUT_OVERFLOW;
  1187.                     return -1;
  1188.                 }
  1189.                 memcpy(agrep_outbuffer+agrep_outpointer, *lastout, curtextbegin-*lastout);
  1190.                 agrep_outpointer += (curtextbegin - *lastout);
  1191.             }
  1192.             *lastout=textbegin;
  1193.             CurrentByteOffset += textbegin - text;
  1194.             text = textbegin;
  1195.         } /* TCOMPRESSED */
  1196.         return 0;
  1197.     }
  1198.  
  1199.     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1200.         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1201.         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1202.         if (agrep_finalfp != NULL)
  1203.             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1204.         else {
  1205.             int outindex;
  1206.             if (prevstring[0] != '\0') {
  1207.                 if(agrep_outpointer + 1 >= agrep_outlen) {
  1208.                     OUTPUT_OVERFLOW;
  1209.                     return -1;
  1210.                 }
  1211.                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1212.             }
  1213.             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1214.                     (CurrentFileName[outindex] != '\0'); outindex++) {
  1215.                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1216.             }
  1217.             if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1218.                 OUTPUT_OVERFLOW;
  1219.                 return -1;
  1220.             }
  1221.             agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1222.             agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1223.             agrep_outpointer += outindex;
  1224.         }
  1225.         NEW_FILE = OFF;
  1226.         PRINTED = 1;
  1227.     }
  1228.  
  1229.     if(BYTECOUNT) {
  1230.         if (agrep_finalfp != NULL)
  1231.             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1232.         else {
  1233.             char s[32];
  1234.             int  outindex;
  1235.             sprintf(s, "%d= ", CurrentByteOffset);
  1236.             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1237.                     (s[outindex] != '\0'); outindex++) {
  1238.                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1239.             }
  1240.             if (s[outindex] != '\0') {
  1241.                 OUTPUT_OVERFLOW;
  1242.                 return -1;
  1243.             }
  1244.             agrep_outpointer += outindex;
  1245.         }
  1246.         PRINTED = 1;
  1247.     }
  1248.  
  1249.     if (PRINTOFFSET) {
  1250.         if (agrep_finalfp != NULL)
  1251.             fprintf(agrep_finalfp, "@%d{%d} ", CurrentByteOffset - (text + oldi-curtextbegin), curtextend-curtextbegin);
  1252.         else {
  1253.             char s[32];
  1254.             int outindex;
  1255.             sprintf(s, "@%d{%d} ", CurrentByteOffset - (text + oldi-curtextbegin), curtextend-curtextbegin);
  1256.             for (outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1257.                      (s[outindex] != '\0'); outindex ++) {
  1258.                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1259.             }
  1260.             if (s[outindex] != '\0') {
  1261.                 OUTPUT_OVERFLOW;
  1262.                 return -1;
  1263.             }
  1264.             agrep_outpointer += outindex;
  1265.         }
  1266.         PRINTED = 1;
  1267.     }
  1268.     if (PRINTRECORD) {
  1269.  
  1270.     if (TCOMPRESSED == ON) {
  1271. #if    MEASURE_TIMES
  1272.         gettimeofday(&initt, NULL);
  1273. #endif    /*MEASURE_TIMES*/
  1274.         if (agrep_finalfp != NULL) {
  1275.             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1276.         }
  1277.         else {
  1278.             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1279.                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1280.                     OUTPUT_OVERFLOW;
  1281.                     return -1;
  1282.                 }
  1283.                 agrep_outpointer += newlen;
  1284.             }
  1285.         }
  1286. #if    MEASURE_TIMES
  1287.         gettimeofday(&finalt, NULL);
  1288.         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1289. #endif    /*MEASURE_TIMES*/
  1290.     }
  1291.     else {
  1292.         if (agrep_finalfp != NULL) {
  1293.             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1294.         }
  1295.         else {
  1296.             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1297.                 OUTPUT_OVERFLOW;
  1298.                 return -1;
  1299.             }
  1300.             memcpy(agrep_outbuffer + agrep_outpointer, curtextbegin, curtextend - curtextbegin);
  1301.             agrep_outpointer += curtextend - curtextbegin;
  1302.         }
  1303.     }
  1304.     }
  1305.     else if (PRINTED) {
  1306.         if (agrep_finalfp != NULL) fputc('\n', agrep_finalfp);
  1307.         else agrep_outbuffer[agrep_outpointer ++] = '\n';
  1308.         PRINTED = 0;
  1309.     }
  1310.     return 0;
  1311. }
  1312.  
  1313. static void
  1314. prep_bm(Pattern, m)      
  1315. unsigned char *Pattern;
  1316. register m;
  1317. {
  1318.     int i;
  1319.     unsigned hash;
  1320.     unsigned char lastc;
  1321.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  1322.     for (i = m-1; i>=0; i--) {
  1323.         hash = TR[Pattern[i]];
  1324.         if((int)(SHIFT[hash]) >= (int)(m - 1)) SHIFT[hash] = m-1-i;
  1325.     }
  1326.     shift_1 = m-1;
  1327.     /* shift_1 records the previous occurrence of the last character of
  1328.     the pattern.  When we match this last character but do not have a match,
  1329.     we can shift until we reach the next occurrence from the right. */
  1330.     lastc = TR[Pattern[m-1]];
  1331.     for (i= m-2; i>=0; i--) {
  1332.         if(TR[Pattern[i]] == lastc )
  1333.         { 
  1334.             shift_1 = m-1 - i;  
  1335.             i = -1; 
  1336.         }
  1337.     }
  1338.     if(shift_1 == 0) shift_1 = 1; /* can never happen - Udi 11/7/94 */
  1339.     if(NOUPPER) for(i=0; i<MAXSYM; i++) {
  1340.         if (isupper(i)) SHIFT[i] = SHIFT[tolower(i)];
  1341.         /* SHIFT[i] = SHIFT[i +  'a' - 'A']; */
  1342.     }
  1343. #ifdef DEBUG
  1344.     for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); 
  1345.     printf("\n");
  1346.     for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); 
  1347.     printf("\n");
  1348. #endif
  1349. }
  1350.  
  1351. /* monkey uses two characters for delta_1 shifting */
  1352.  
  1353. CHARTYPE SHIFT_2[MAX_SHIFT_2];
  1354.  
  1355. int
  1356. monkey( pat, m, text, textend  ) 
  1357. register int m  ; 
  1358. register CHARTYPE *text, *textend, *pat;
  1359. {
  1360.     int PRINTED = 0;
  1361.     register unsigned hash;
  1362.     register CHARTYPE shift;
  1363.     register int  m1, j; 
  1364.     CHARTYPE *textbegin = text;
  1365.     CHARTYPE *textstart;
  1366.     int newlen;
  1367.     CHARTYPE *curtextbegin;
  1368.     CHARTYPE *curtextend;
  1369. #if    MEASURE_TIMES
  1370.     struct timeval initt, finalt;
  1371. #endif
  1372.     CHARTYPE *lastout = text;
  1373.  
  1374.     m1 = m - 1;
  1375.     text = text+m1;
  1376.     CurrentByteOffset += m1;
  1377.     while (text < textend) {
  1378.         textstart = text;
  1379.         hash = TR[*text];
  1380.         hash = (hash << 3) + TR[*(text-1)];
  1381.         shift = SHIFT_2[hash];
  1382.         while(shift) {
  1383.             text = text + shift;
  1384.             hash = (TR[*text] << 3) + TR[*(text-1)];
  1385.             shift = SHIFT_2[hash];
  1386.         }
  1387.         CurrentByteOffset += text - textstart;
  1388.         j = 0;
  1389.         while(TR[pat[m1 - j]] == TR[*(text - j)]) { 
  1390.             if(++j == m) break; 
  1391.         }
  1392.         if (j == m ) {
  1393.             if(text > textend) return 0; /* Udi: used to be >= for some reason */
  1394.             /* added by Udi 11/7/94 */
  1395.             if(WORDBOUND) {
  1396.                 if(isalnum(*(text+1))) goto CONT;    /* as if there was no match */
  1397.                 if(isalnum(*(text-m))) goto CONT;    /* as if there was no match */
  1398.                 /* changed by Udi 11/7/94 to avoid having to set TR[] to W_delim */
  1399.             }
  1400.  
  1401.             if (TCOMPRESSED == ON) {
  1402.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1403.                 if (!DELIMITER) {
  1404.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1405.                     if (*curtextbegin == '\n') curtextbegin ++;
  1406.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1407.                     if (*curtextend == '\n') curtextend ++;
  1408.                 }
  1409.                 else {
  1410.                     curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  1411.                     curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1412.                 }
  1413.             }
  1414.             else {
  1415.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1416.                 if (!DELIMITER) {
  1417.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1418.                     if (*curtextbegin == '\n') curtextbegin ++;
  1419.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1420.                     if (*curtextend == '\n') curtextend ++;
  1421.                 }
  1422.                 else {
  1423.                     curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  1424.                     curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  1425.                 }
  1426.             }
  1427.  
  1428.             if (TCOMPRESSED == ON) {
  1429. #if     MEASURE_TIMES
  1430.                                 gettimeofday(&initt, NULL);
  1431. #endif  /*MEASURE_TIMES*/
  1432.                 if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text - curtextbegin + m, EASYSEARCH))
  1433.                     goto CONT;    /* as if there was no match */
  1434. #if     MEASURE_TIMES
  1435.                                 gettimeofday(&finalt, NULL);
  1436.                                 FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1437. #endif  /*MEASURE_TIMES*/
  1438.             }
  1439.  
  1440.             textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1441.             num_of_matched++;
  1442.             if(FILENAMEONLY)  return 0;
  1443.             if (!COUNT) {
  1444.                 if (!INVERSE) {
  1445.                     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1446.                         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1447.                         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1448.                         if (agrep_finalfp != NULL)
  1449.                             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1450.                         else {
  1451.                             int outindex;
  1452.                             if (prevstring[0] != '\0') {
  1453.                                 if(agrep_outpointer + 1 >= agrep_outlen) {
  1454.                                     OUTPUT_OVERFLOW;
  1455.                                     return -1;
  1456.                                 }
  1457.                                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1458.                             }
  1459.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1460.                                     (CurrentFileName[outindex] != '\0'); outindex++) {
  1461.                                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1462.                             }
  1463.                             if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1464.                                 OUTPUT_OVERFLOW;
  1465.                                 return -1;
  1466.                             }
  1467.                             agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1468.                             agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1469.                             agrep_outpointer += outindex;
  1470.                         }
  1471.                         NEW_FILE = OFF;
  1472.                         PRINTED = 1;
  1473.                     }
  1474.  
  1475.                     if(BYTECOUNT) {
  1476.                         if (agrep_finalfp != NULL)
  1477.                             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1478.                         else {
  1479.                             char s[32];
  1480.                             int  outindex;
  1481.                             sprintf(s, "%d= ", CurrentByteOffset);
  1482.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1483.                                     (s[outindex] != '\0'); outindex++) {
  1484.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1485.                             }
  1486.                             if (s[outindex] != '\0') {
  1487.                                 OUTPUT_OVERFLOW;
  1488.                                 return -1;
  1489.                             }
  1490.                             agrep_outpointer += outindex;
  1491.                         }
  1492.                         PRINTED = 1;
  1493.                     }
  1494.  
  1495.                     if (PRINTOFFSET) {
  1496.                         if (agrep_finalfp != NULL)
  1497.                             fprintf(agrep_finalfp, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  1498.                         else {
  1499.                             char s[32];
  1500.                             int outindex;
  1501.                             sprintf(s, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  1502.                             for (outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1503.                                      (s[outindex] != '\0'); outindex ++) {
  1504.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1505.                             }
  1506.                             if (s[outindex] != '\0') {
  1507.                                 OUTPUT_OVERFLOW;
  1508.                                 return -1;
  1509.                             }
  1510.                             agrep_outpointer += outindex;
  1511.                         }
  1512.                         PRINTED = 1;
  1513.                     }
  1514.  
  1515.                     CurrentByteOffset += textbegin - text;
  1516.                     text = textbegin;
  1517.  
  1518.                     if (PRINTRECORD) {
  1519.                     if (TCOMPRESSED == ON) {
  1520. #if    MEASURE_TIMES
  1521.                         gettimeofday(&initt, NULL);
  1522. #endif    /*MEASURE_TIMES*/
  1523.                         if (agrep_finalfp != NULL)
  1524.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1525.                         else {
  1526.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1527.                                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1528.                                     OUTPUT_OVERFLOW;
  1529.                                     return -1;
  1530.                                 }
  1531.                                 agrep_outpointer += newlen;
  1532.                             }
  1533.                         }
  1534. #if    MEASURE_TIMES
  1535.                         gettimeofday(&finalt, NULL);
  1536.                         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1537. #endif    /*MEASURE_TIMES*/
  1538.                     }
  1539.                     else {
  1540.                         if (agrep_finalfp != NULL) {
  1541.                             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1542.                         }
  1543.                         else {
  1544.                             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1545.                                 OUTPUT_OVERFLOW;
  1546.                                 return -1;
  1547.                             }
  1548.                             memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  1549.                             agrep_outpointer += curtextend - curtextbegin;
  1550.                         }
  1551.                     }
  1552.                     }
  1553.                     else if (PRINTED) {
  1554.                         if (agrep_finalfp != NULL) fputc('\n', agrep_finalfp);
  1555.                         else agrep_outbuffer[agrep_outpointer ++] = '\n';
  1556.                         PRINTED = 0;
  1557.                     }
  1558.                 }
  1559.                 else {    /* INVERSE */
  1560.                     if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1561.                         if (agrep_finalfp != NULL)
  1562.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  1563.                         else {
  1564.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1565.                                 if (newlen + agrep_outpointer >= agrep_outlen) {
  1566.                                     OUTPUT_OVERFLOW;
  1567.                                     return -1;
  1568.                                 }
  1569.                                 agrep_outpointer += newlen;
  1570.                             }
  1571.                         }
  1572.                         lastout=textbegin;
  1573.                         CurrentByteOffset += textbegin - text;
  1574.                         text = textbegin;
  1575.                     }
  1576.                     else { /* NOT TCOMPRESSED */
  1577.                         if (agrep_finalfp != NULL)
  1578.                             fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  1579.                         else {
  1580.                             if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  1581.                                 OUTPUT_OVERFLOW;
  1582.                                 return -1;
  1583.                             }
  1584.                             memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  1585.                             agrep_outpointer += (curtextbegin - lastout);
  1586.                         }
  1587.                         lastout=textbegin;
  1588.                         CurrentByteOffset += textbegin - text;
  1589.                         text = textbegin;
  1590.                     } /* TCOMPRESSED */
  1591.                 } /* INVERSE */
  1592.             }
  1593.             else {    /* COUNT */
  1594.                 CurrentByteOffset += textbegin - text;
  1595.                 text = textbegin;
  1596.             }
  1597.  
  1598.             /* Counteract the ++ below */
  1599.             text --;
  1600.             CurrentByteOffset --;
  1601.             if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  1602.                 ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  1603.         }
  1604.     CONT:
  1605.         text++;
  1606.         CurrentByteOffset ++;
  1607.     }
  1608.  
  1609.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1610.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1611.             if (agrep_finalfp != NULL)
  1612.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1613.             else {
  1614.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1615.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1616.                         OUTPUT_OVERFLOW;
  1617.                         return -1;
  1618.                     }
  1619.                     agrep_outpointer += newlen;
  1620.                 }
  1621.             }
  1622.         }
  1623.         else { /* NOT TCOMPRESSED */
  1624.             if (agrep_finalfp != NULL)
  1625.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1626.             else {
  1627.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1628.                     OUTPUT_OVERFLOW;
  1629.                     return -1;
  1630.                 }
  1631.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1632.                 agrep_outpointer += (textend - lastout + 1);
  1633.             }
  1634.         } /* TCOMPRESSED */
  1635.     }
  1636.  
  1637.     return 0;
  1638. }
  1639.  
  1640. /* a_monkey() the approximate monkey move */
  1641. int
  1642. a_monkey( pat, m, text, textend, D ) 
  1643. register int m, D ; 
  1644. register CHARTYPE *text, *textend, *pat;
  1645. {
  1646.     int PRINTED = 0;
  1647.     register CHARTYPE *oldtext;
  1648.     CHARTYPE *curtextbegin;
  1649.     CHARTYPE *curtextend;
  1650.     register unsigned hash, hashmask, suffix_error; 
  1651.     register int  m1 = m-1-D, pos; 
  1652.     CHARTYPE *textbegin = text;
  1653.     CHARTYPE *textstart;
  1654.     CHARTYPE *lastout = text;
  1655.     int newlen;
  1656.  
  1657.     hashmask = Hashmask;
  1658.     oldtext  = text;
  1659.     while (text < textend) {
  1660.         textstart = text;
  1661.         text = text+m1;
  1662.         suffix_error = 0;
  1663.         while(suffix_error <= D) {
  1664.             hash = *text--;
  1665.             while(MEMBER_1[hash]) {
  1666.                 hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
  1667.             }
  1668.             suffix_error++;
  1669.         }
  1670.         CurrentByteOffset += text - textstart;
  1671.         if(text <= oldtext) {
  1672.             if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  1673.                 CurrentByteOffset += (oldtext+pos - text);
  1674.                 text = oldtext+pos;
  1675.                 if(text > textend) return 0;
  1676.  
  1677.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1678.                 if (TCOMPRESSED == ON) {
  1679.                     if (!DELIMITER) {
  1680.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1681.                         if (*curtextbegin == '\n') curtextbegin ++;
  1682.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1683.                         if (*curtextend == '\n') curtextend ++;
  1684.                     }
  1685.                     else {
  1686.                         curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  1687.                         curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1688.                     }
  1689.                 }
  1690.                 else {
  1691.                     if (!DELIMITER) {
  1692.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1693.                         if (*curtextbegin == '\n') curtextbegin ++;
  1694.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1695.                         if (*curtextend == '\n') curtextend ++;
  1696.                     }
  1697.                     else {
  1698.                         curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  1699.                         curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  1700.                     }
  1701.                 }
  1702.                 textbegin = curtextend; /* (curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1703.  
  1704.                 num_of_matched++;
  1705.                 if(FILENAMEONLY) return 0;
  1706.                 if(!COUNT) {
  1707.                     if (!INVERSE) {
  1708.                         if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1709.                             char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1710.                             char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1711.                             if (agrep_finalfp != NULL)
  1712.                                 fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1713.                             else {
  1714.                                 int outindex;
  1715.                                 if (prevstring[0] != '\0') {
  1716.                                     if(agrep_outpointer + 1 >= agrep_outlen) {
  1717.                                         OUTPUT_OVERFLOW;
  1718.                                         return -1;
  1719.                                     }
  1720.                                     else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1721.                                 }
  1722.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1723.                                         (CurrentFileName[outindex] != '\0'); outindex++) {
  1724.                                     agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1725.                                 }
  1726.                                 if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1727.                                     OUTPUT_OVERFLOW;
  1728.                                     return -1;
  1729.                                 }
  1730.                                 agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1731.                                 agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1732.                                 agrep_outpointer += outindex;
  1733.                             }
  1734.                             NEW_FILE = OFF;
  1735.                             PRINTED = 1;
  1736.                         }
  1737.  
  1738.                         if(BYTECOUNT) {
  1739.                             if (agrep_finalfp != NULL)
  1740.                                 fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1741.                             else {
  1742.                                 char s[32];
  1743.                                 int  outindex;
  1744.                                 sprintf(s, "%d= ", CurrentByteOffset);
  1745.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1746.                                         (s[outindex] != '\0'); outindex++) {
  1747.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1748.                                 }
  1749.                                 if (s[outindex] != '\0') {
  1750.                                     OUTPUT_OVERFLOW;
  1751.                                     return -1;
  1752.                                 }
  1753.                                 agrep_outpointer += outindex;
  1754.                             }
  1755.                             PRINTED = 1;
  1756.                         }
  1757.  
  1758.                         if (PRINTOFFSET) {
  1759.                             if (agrep_finalfp != NULL)
  1760.                                 fprintf(agrep_finalfp, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  1761.                             else {
  1762.                                 char s[32];
  1763.                                 int outindex;
  1764.                                 sprintf(s, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  1765.                                 for (outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1766.                                          (s[outindex] != '\0'); outindex ++) {
  1767.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1768.                                 }
  1769.                                 if (s[outindex] != '\0') {
  1770.                                     OUTPUT_OVERFLOW;
  1771.                                     return -1;
  1772.                                 }
  1773.                                 agrep_outpointer += outindex;
  1774.                             }
  1775.                             PRINTED = 1;
  1776.                         }
  1777.  
  1778.                         CurrentByteOffset += textbegin - text;
  1779.                         text = textbegin;
  1780.  
  1781.                         if (PRINTRECORD) {
  1782.                         if (TCOMPRESSED == ON) {
  1783. #if    MEASURE_TIMES
  1784.                             gettimeofday(&initt, NULL);
  1785. #endif    /*MEASURE_TIMES*/
  1786.                             if (agrep_finalfp != NULL)
  1787.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1788.                             else {
  1789.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1790.                                     if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1791.                                         OUTPUT_OVERFLOW;
  1792.                                         return -1;
  1793.                                     }
  1794.                                     agrep_outpointer += newlen;
  1795.                                 }
  1796.                             }
  1797. #if    MEASURE_TIMES
  1798.                             gettimeofday(&finalt, NULL);
  1799.                             OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1800. #endif    /*MEASURE_TIMES*/
  1801.                         }
  1802.                         else {
  1803.                             if (agrep_finalfp != NULL) {
  1804.                                 fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1805.                             }
  1806.                             else {
  1807.                                 if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1808.                                     OUTPUT_OVERFLOW;
  1809.                                     return -1;
  1810.                                 }
  1811.                                 memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  1812.                                 agrep_outpointer += curtextend - curtextbegin;
  1813.                             }
  1814.                         }
  1815.                         }
  1816.                         else if (PRINTED) {
  1817.                             if (agrep_finalfp != NULL) fputc('\n', agrep_finalfp);
  1818.                             else agrep_outbuffer[agrep_outpointer ++] = '\n';
  1819.                             PRINTED = 0;
  1820.                         }
  1821.                     }
  1822.                     else {    /* INVERSE */
  1823.                         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1824.                             if (agrep_finalfp != NULL)
  1825.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  1826.                             else {
  1827.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1828.                                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1829.                                         OUTPUT_OVERFLOW;
  1830.                                         return -1;
  1831.                                     }
  1832.                                     agrep_outpointer += newlen;
  1833.                                 }
  1834.                             }
  1835.                             lastout=textbegin;
  1836.                             CurrentByteOffset += textbegin - text;
  1837.                             text = textbegin;
  1838.                         }
  1839.                         else { /* NOT TCOMPRESSED */
  1840.                             if (agrep_finalfp != NULL)
  1841.                                 fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  1842.                             else {
  1843.                                 if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  1844.                                     OUTPUT_OVERFLOW;
  1845.                                     return -1;
  1846.                                 }
  1847.                                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  1848.                                 agrep_outpointer += (curtextbegin - lastout);
  1849.                             }
  1850.                             lastout=textbegin;
  1851.                             CurrentByteOffset += textbegin - text;
  1852.                             text = textbegin;
  1853.                         } /* TCOMPRESSED */
  1854.                     }
  1855.                 }
  1856.                 else {    /* COUNT */
  1857.                     CurrentByteOffset += textbegin - text;
  1858.                     text = textbegin;
  1859.                 }
  1860.                 if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  1861.                     ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  1862.             }
  1863.             else {
  1864.                 CurrentByteOffset += (oldtext + m - text);
  1865.                 text = oldtext + m;
  1866.             }
  1867.         }
  1868.         oldtext = text;
  1869.     }
  1870.  
  1871.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1872.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1873.             if (agrep_finalfp != NULL)
  1874.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1875.             else {
  1876.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1877.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1878.                         OUTPUT_OVERFLOW;
  1879.                         return -1;
  1880.                     }
  1881.                     agrep_outpointer += newlen;
  1882.                 }
  1883.             }
  1884.         }
  1885.         else { /* NOT TCOMPRESSED */
  1886.             if (agrep_finalfp != NULL)
  1887.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1888.             else {
  1889.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1890.                     OUTPUT_OVERFLOW;
  1891.                     return -1;
  1892.                 }
  1893.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1894.                 agrep_outpointer += (textend - lastout + 1);
  1895.             }
  1896.         } /* TCOMPRESSED */
  1897.     }
  1898.  
  1899.     return 0;
  1900. }
  1901.  
  1902. static void
  1903. am_preprocess(Pattern)
  1904. CHARTYPE *Pattern;
  1905. {
  1906.     int i, m;
  1907.     m = strlen(Pattern);
  1908.     for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
  1909.     for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
  1910.     for (i = m-1; i>=0; i--) {
  1911.         MEMBER_1[Pattern[i]] = 1;
  1912.     }
  1913.     for (i = m-1; i > 0; i--) {
  1914.         MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
  1915.     }
  1916. }
  1917.  
  1918. int
  1919. verify(m, n, D, pat, text)
  1920. register int m, n, D;
  1921. CHARTYPE *pat, *text;
  1922. {   
  1923.     int A[MAXPATT], B[MAXPATT];
  1924.     register int last = D;      
  1925.     register int cost = 0;  
  1926.     register int k, i, c;
  1927.     register int m1 = m+1;
  1928.     CHARTYPE *textend = text+n;
  1929.     CHARTYPE *textbegin = text;
  1930.  
  1931.     for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
  1932.     while (text < textend)
  1933.     {
  1934.         for (k = 1; k <= last; k++)
  1935.         {
  1936.             cost = B[k-1]+1; 
  1937.             if (pat[k-1] != *text)
  1938.             {   
  1939.                 if (B[k]+1 < cost) cost = B[k]+1; 
  1940.                 if (A[k-1]+1 < cost) cost = A[k-1]+1; 
  1941.             }
  1942.             else cost = cost -1; 
  1943.             A[k] = cost; 
  1944.         }
  1945.         if(pat[last] == *text++) { 
  1946.             A[last+1] = B[last]; 
  1947.             last++; 
  1948.         }
  1949.         if(A[last] < D) A[last+1] = A[last++]+1;
  1950.         while (A[last] > D) last = last - 1;
  1951.         if(last >= m) return(text - textbegin - 1);
  1952.         if(*text == '\n') {
  1953.             last = D;
  1954.             for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1955.         }
  1956.         for (k = 1; k <= last; k++)
  1957.         {
  1958.             cost = A[k-1]+1; 
  1959.             if (pat[k-1] != *text)
  1960.             {   
  1961.                 if (A[k]+1 < cost) cost = A[k]+1; 
  1962.                 if (B[k-1]+1 < cost) cost = B[k-1]+1; 
  1963.             }
  1964.             else cost = cost -1; 
  1965.             B[k] = cost;
  1966.         }
  1967.         if(pat[last] == *text++) { 
  1968.             B[last+1] = A[last]; 
  1969.             last++; 
  1970.         }
  1971.         if(B[last] < D) B[last+1] = B[last++]+1;
  1972.         while (B[last] > D) last = last -1;
  1973.         if(last >= m)   return(text - textbegin - 1);
  1974.         if(*text == '\n') {
  1975.             last = D;
  1976.             for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1977.         }
  1978.     }    
  1979.     return(0);
  1980. }
  1981.  
  1982. /* preprocessing for monkey()   */
  1983. static void
  1984. m_preprocess(Pattern)
  1985. CHARTYPE *Pattern;
  1986. {
  1987.     int i, j, m;
  1988.     unsigned hash;
  1989.     m = strlen(Pattern);
  1990.     for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
  1991.     for (i = m-1; i>=1; i--) {
  1992.         hash = TR[Pattern[i]];
  1993.         hash = hash << 3;
  1994.         for (j = 0; j< MAXSYM; j++) {
  1995.             if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
  1996.         }
  1997.         hash = hash + TR[Pattern[i-1]];
  1998.         if((int)(SHIFT_2[hash]) >= (int)(m - 1)) SHIFT_2[hash] = m-1-i;
  1999.     }
  2000.     shift_1 = m-1;
  2001.     for (i= m-2; i>=0; i--) {
  2002.         if(TR[Pattern[i]] == TR[Pattern[m-1]] )
  2003.         { 
  2004.             shift_1 = m-1 - i;  
  2005.             i = -1; 
  2006.         }
  2007.     }
  2008.     if(shift_1 == 0) shift_1 = 1;
  2009.     SHIFT_2[0] = 0;
  2010. }
  2011.  
  2012. /* monkey4() the approximate monkey move */
  2013.  
  2014. char *MEMBER_D = NULL;
  2015.  
  2016. int
  2017. monkey4( pat, m, text, textend, D  ) 
  2018. register int m, D ; 
  2019. register unsigned char *text, *pat, *textend;
  2020. {
  2021.     int PRINTED = 0;
  2022.     register unsigned char *oldtext;
  2023.     register unsigned hash, hashmask, suffix_error; 
  2024.     register int m1=m-1-D, pos; 
  2025.     CHARTYPE *textbegin = text;
  2026.     CHARTYPE *textstart;
  2027.     CHARTYPE *curtextbegin;
  2028.     CHARTYPE *curtextend;
  2029.     CHARTYPE *lastout = text;
  2030.     int newlen;
  2031.  
  2032.     hashmask = Hashmask;
  2033.     oldtext = text ;
  2034.     while (text < textend) {
  2035.         textstart = text;
  2036.         text = text + m1;
  2037.         suffix_error = 0;
  2038.         while(suffix_error <= D) {
  2039.             hash = char_map[*text--];
  2040.             hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  2041.             while(MEMBER_D[hash]) {
  2042.                 hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  2043.             }
  2044.             suffix_error++;
  2045.         }
  2046.         CurrentByteOffset += text - textstart;
  2047.         if(text <= oldtext) {
  2048.             if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  2049.                 CurrentByteOffset += (oldtext+pos - text);
  2050.                 text = oldtext+pos;
  2051.                 if(text > textend) return 0;
  2052.  
  2053.                 if (TCOMPRESSED == ON) {
  2054.                     /* Don't update CurrentByteOffset here: only before outputting properly */
  2055.                     if (!DELIMITER) {
  2056.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  2057.                         if (*curtextbegin == '\n') curtextbegin ++;
  2058.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  2059.                         if (*curtextend == '\n') curtextend ++;
  2060.                     }
  2061.                     else {
  2062.                         curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  2063.                         curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  2064.                     }
  2065.                 }
  2066.                 else {
  2067.                     /* Don't update CurrentByteOffset here: only before outputting properly */
  2068.                     if (!DELIMITER) {
  2069.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  2070.                         if (*curtextbegin == '\n') curtextbegin ++;
  2071.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  2072.                         if (*curtextend == '\n') curtextend ++;
  2073.                     }
  2074.                     else {
  2075.                         curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  2076.                         curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  2077.                     }
  2078.                 }
  2079.                 textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  2080.  
  2081.                 num_of_matched++;
  2082.                 if(FILENAMEONLY) return 0;
  2083.                 if(!COUNT) {
  2084.                     if (!INVERSE) {
  2085.                         if(FNAME && (NEW_FILE || !POST_FILTER)) {
  2086.                             char    nextchar = (POST_FILTER == ON)?'\n':' ';
  2087.                             char    *prevstring = (POST_FILTER == ON)?"\n":"";
  2088.                             if (agrep_finalfp != NULL)
  2089.                                 fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  2090.                             else {
  2091.                                 int outindex;
  2092.                                 if (prevstring[0] != '\0') {
  2093.                                     if(agrep_outpointer + 1 >= agrep_outlen) {
  2094.                                         OUTPUT_OVERFLOW;
  2095.                                         return -1;
  2096.                                     }
  2097.                                     else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  2098.                                 }
  2099.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  2100.                                         (CurrentFileName[outindex] != '\0'); outindex++) {
  2101.                                     agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  2102.                                 }
  2103.                                 if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  2104.                                     OUTPUT_OVERFLOW;
  2105.                                     return -1;
  2106.                                 }
  2107.                                 agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  2108.                                 agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  2109.                                 agrep_outpointer += outindex;
  2110.                             }
  2111.                             NEW_FILE = OFF;
  2112.                             PRINTED = 1;
  2113.                         }
  2114.  
  2115.                         if(BYTECOUNT) {
  2116.                             if (agrep_finalfp != NULL)
  2117.                                 fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  2118.                             else {
  2119.                                 char s[32];
  2120.                                 int  outindex;
  2121.                                 sprintf(s, "%d= ", CurrentByteOffset);
  2122.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  2123.                                         (s[outindex] != '\0'); outindex++) {
  2124.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  2125.                                 }
  2126.                                 if (s[outindex] != '\0') {
  2127.                                     OUTPUT_OVERFLOW;
  2128.                                     return -1;
  2129.                                 }
  2130.                                 agrep_outpointer += outindex;
  2131.                             }
  2132.                             PRINTED = 1;
  2133.                         }
  2134.  
  2135.                         if (PRINTOFFSET) {
  2136.                             if (agrep_finalfp != NULL)
  2137.                                 fprintf(agrep_finalfp, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  2138.                             else {
  2139.                                 char s[32];
  2140.                                 int outindex;
  2141.                                 sprintf(s, "@%d{%d} ", CurrentByteOffset - (text -curtextbegin), curtextend-curtextbegin);
  2142.                                 for (outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  2143.                                          (s[outindex] != '\0'); outindex ++) {
  2144.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  2145.                                 }
  2146.                                 if (s[outindex] != '\0') {
  2147.                                     OUTPUT_OVERFLOW;
  2148.                                     return -1;
  2149.                                 }
  2150.                                 agrep_outpointer += outindex;
  2151.                             }
  2152.                             PRINTED = 1;
  2153.                         }
  2154.  
  2155.                         CurrentByteOffset += textbegin + 1 - text;
  2156.                         text = textbegin + 1;
  2157.  
  2158.                         if (PRINTRECORD) {
  2159.                         if (TCOMPRESSED == ON) {
  2160. #if    MEASURE_TIMES
  2161.                             gettimeofday(&initt, NULL);
  2162. #endif    /*MEASURE_TIMES*/
  2163.                             if (agrep_finalfp != NULL)
  2164.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  2165.                             else {
  2166.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  2167.                                     if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  2168.                                         OUTPUT_OVERFLOW;
  2169.                                         return -1;
  2170.                                     }
  2171.                                     agrep_outpointer += newlen;
  2172.                                 }
  2173.                             }
  2174. #if    MEASURE_TIMES
  2175.                             gettimeofday(&finalt, NULL);
  2176.                             OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  2177. #endif    /*MEASURE_TIMES*/
  2178.                         }
  2179.                         else {
  2180.                             if (agrep_finalfp != NULL) {
  2181.                                 fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  2182.                             }
  2183.                             else {
  2184.                                 if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  2185.                                     OUTPUT_OVERFLOW;
  2186.                                     return -1;
  2187.                                 }
  2188.                                 memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  2189.                                 agrep_outpointer += curtextend - curtextbegin;
  2190.                             }
  2191.                         }
  2192.                         }
  2193.                         else if (PRINTED) {
  2194.                             if (agrep_finalfp != NULL) fputc('\n', agrep_finalfp);
  2195.                             else agrep_outbuffer[agrep_outpointer ++] = '\n';
  2196.                             PRINTED = 0;
  2197.                         }
  2198.                     }
  2199.                     else {    /* INVERSE */
  2200.                         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  2201.                             if (agrep_finalfp != NULL)
  2202.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  2203.                             else {
  2204.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  2205.                                     if (newlen + agrep_outpointer >= agrep_outlen) {
  2206.                                         OUTPUT_OVERFLOW;
  2207.                                         return -1;
  2208.                                     }
  2209.                                     agrep_outpointer += newlen;
  2210.                                 }
  2211.                             }
  2212.                             lastout=textbegin;
  2213.                             CurrentByteOffset += textbegin + 1 - text;
  2214.                             text = textbegin + 1;
  2215.                         }
  2216.                         else { /* NOT TCOMPRESSED */
  2217.                             if (agrep_finalfp != NULL)
  2218.                                 fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  2219.                             else {
  2220.                                 if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  2221.                                     OUTPUT_OVERFLOW;
  2222.                                     return -1;
  2223.                                 }
  2224.                                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  2225.                                 agrep_outpointer += (curtextbegin - lastout);
  2226.                             }
  2227.                             lastout=textbegin;
  2228.                             CurrentByteOffset += textbegin + 1 - text;
  2229.                             text = textbegin + 1;
  2230.                         } /* TCOMPRESSED */
  2231.                     }
  2232.                 }
  2233.                 else {    /* COUNT */
  2234.                     CurrentByteOffset += textbegin + 1 - text;
  2235.                     text = textbegin + 1 ;
  2236.                 }
  2237.                 if (((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) ||
  2238.                     ((LIMITPERFILE > 0) && (LIMITPERFILE <= num_of_matched - prev_num_of_matched))) return 0;    /* done */
  2239.             }
  2240.             else { CurrentByteOffset += (oldtext + m - text); text = oldtext + m; }
  2241.         }
  2242.         oldtext = text; 
  2243.     }
  2244.  
  2245.     if (INVERSE && !COUNT && (lastout <= textend)) {
  2246.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  2247.             if (agrep_finalfp != NULL)
  2248.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  2249.             else {
  2250.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  2251.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  2252.                         OUTPUT_OVERFLOW;
  2253.                         return -1;
  2254.                     }
  2255.                     agrep_outpointer += newlen;
  2256.                 }
  2257.             }
  2258.         }
  2259.         else { /* NOT TCOMPRESSED */
  2260.             if (agrep_finalfp != NULL)
  2261.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  2262.             else {
  2263.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  2264.                     OUTPUT_OVERFLOW;
  2265.                     return -1;
  2266.                 }
  2267.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  2268.                 agrep_outpointer += (textend - lastout + 1);
  2269.             }
  2270.         } /* TCOMPRESSED */
  2271.     }
  2272.  
  2273.     return 0;
  2274. }
  2275.  
  2276. static void
  2277. prep4(Pattern, m)
  2278. char *Pattern; 
  2279. int m;
  2280. {
  2281.     int i, j, k;
  2282.     unsigned hash;
  2283.  
  2284.     for(i=0; i< MAXSYM; i++) char_map[i] = 0;
  2285.     char_map['a'] = char_map['A'] = 4;
  2286.     char_map['g'] = char_map['g'] = 1;
  2287.     char_map['t'] = char_map['t'] = 2;
  2288.     char_map['c'] = char_map['c'] = 3;
  2289.     char_map['n'] = char_map['n'] = 5;
  2290.  
  2291.     BSize = blog(4, m);
  2292.     for (i = 1, Hashmask = 1 ; i<(int)(BSize*LOG_DNA); i++) Hashmask = (Hashmask << 1) + 1 ;
  2293.     if (MEMBER_D != NULL) free(MEMBER_D);
  2294.     MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
  2295. #ifdef DEBUG
  2296.     printf("BSize = %d", BSize);
  2297. #endif 
  2298.     for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
  2299.     for (j=0; j < (int)BSize; j++) {
  2300.         for(i=m-1; i >= j; i--) {
  2301.             hash = 0;
  2302.             for(k=0; k <= j; k++) 
  2303.                 hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
  2304. #ifdef DEBUG
  2305.             printf("< %d >, ", hash);
  2306. #endif
  2307.             MEMBER_D[hash] = 1;
  2308.         }
  2309.     }
  2310. }
  2311.  
  2312. int
  2313. blog(base, m )
  2314. int base, m;
  2315. {
  2316.     int i, exp;
  2317.     exp = base;
  2318.     m = m + m/2;
  2319.     for (i = 1; exp < m; i++) exp = exp * base;
  2320.     return(i);
  2321. }
  2322.  
  2323.